package com.example.lcpractice.lc;

import com.example.lcpractice.datastructure.ListNode;

/**
 * [198]打家劫舍.java
 * /你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上
 * //被小偷闯入，系统会自动报警。
 * //
 * // 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
 * //
 * //
 * //
 * // 示例 1：
 * //
 * //
 * //输入：[1,2,3,1]
 * //输出：4
 * //解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
 * //     偷窃到的最高金额 = 1 + 3 = 4 。
 * //
 * // 示例 2：
 * //
 * //
 * //输入：[2,7,9,3,1]
 * //输出：12
 * //解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
 * //     偷窃到的最高金额 = 2 + 9 + 1 = 12 。
 * //
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // 1 <= nums.length <= 100
 * // 0 <= nums[i] <= 400
 * //
 * // Related Topics 数组 动态规划 👍 2314 👎 0
 */
public class Lc198 {


    public static void main(String[] args) {

    }

    /**
     * 1. 子问题：
     * 只考虑前两个房间时，谁大选谁
     * 考虑第三个房间
     * 如果偷第三个房间，则意味着第二个房间不投，也就是第三个房间值 + 第一个房间的宝藏数量
     * 如果不偷第三个房间，则宝藏数量等于前两个房间宝藏数量
     *
     *<br>
     * 2. 确认状态：
     * int [] nums; // 各个房间的宝藏数
     *
     * int [] flags = new int [n]; // 记录各个房间有没有被偷，若flag = 0 则没偷， flag = 1 则偷了。
     *
     * <br>
     * <u>dp[i]表示前i个房间偷到的最大宝藏数</u><br>
     * <u> <b>递归重要</b>dp[i]表示考虑前i个房间偷到的最大宝藏数，如dp[i-1]视为不考虑第i个房间</u><br>
     * int [] dp = new int [n]; <br>
     * 3. 初始状态：<br>
     * 一个房间求dp[0]：<br>
     *  dp[0] = nums[0] ; flags[0] = 1;<br>
     *
     * 两个房间求dp[1]：<br>
     * dp[1]=max{nums[0],nums[1]}<br>
     * Condition 1( 1yes, 2no ) ：flags[1] = 0; dp[1] =nums[0];<br>
     * Condition 2( 1no, 2yes )： flags[1] = 1; dp[1] =num[1];<br>
     * 选 Condition 1 还是 Condition 2呢？ 比较 两种情况下dp[1]的大小
     *
     * 三个房间求dp[2]:<br>
     * Condition 1( 1yes, 2no ) ：flags[2]=1, dp[2]=nums[2]+dp[0] **考虑第3，则加上不考虑第2的dp[0]
     * <br>
     * Condition 2( 1no, 2yes ) ：flags[2]=0, dp[2]=dp[1] **不考虑第3的最大即dp[1]
     *
     * 四个房间求dp[3]:<br>
     * Condition 1( 1yes, 2no ) ：flags[3]=1, dp[3]=nums[3]+nums[nums] **考虑第4，则加上不考虑第3的dp[2]
     * <br>
     * Condition 2( 1no, 2yes ) ：flags[3]=0, dp[3]=dp[2] **不考虑第4房间的最大即dp[2]
     *
     * 推广到前i个房间: (i>=2)
     * 如果当前i需要被偷
     * 第i个不选，则视为只考虑i-1个的最大值<br>
     * <b>选中第i个，则加上不选i-1的最大值</b><br>
     * <u>when flags[i] = 1, dp[i] = nums[i] + dp[i-2]</u><br>
     * <b>第i个不选，则视为只考虑i-1个的最大值</b><br>
     * <u>when flags[i] = 0; dp[i] = dp[i-1]</u><br>
     * 4. 状态转移方程：
     * dp[0] = nums[0];
     * dp[1] = max(nums[0],nums[1]);
     * for(int i = 2;i<n;i++)
     *     dp[i] = max(nums[i] + dp[i-2],dp[i-1])
     * @param nums
     * @return
     */
    public static int rob(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        if (nums.length == 1) {
            return dp[0];
        }
        dp[1] = nums[1] > nums[0] ? nums[1] : nums[0];
        for (int i = 2; i < nums.length; i++) {
            int curNeed=nums[i]+dp[i-2];
            int curNoNeed=dp[i-1];
            if(curNeed>curNoNeed){
                dp[i] = curNeed;
            }else {
                dp[i] = curNoNeed;
            }
        }
        return dp[nums.length-1];
    }
}
